import java.util.HashMap;
import java.util.Map;

/**
 * @author zhaozeyang
 * @date 2018/11/1 16:39
 * @description
 */
public class 阶梯问题 {


    public static void main(String[] args) {
        long a = System.currentTimeMillis();
        System.out.println(f(1000, new HashMap<Integer, Integer>()));
        long b = System.currentTimeMillis();

        System.out.println(f2(10000));
        long c = System.currentTimeMillis();
        System.out.println((b - a) + "----" + (c - b));

        System.out.println(getMostGold(5, 10, new int[]{200, 300, 350, 400, 500}, new int[]{3, 4, 3, 5, 5}));

    }

    //2^n
    private static int f(int i, Map<Integer, Integer> map) {
        if (i == 1) {
            return 1;
        }
        if (i == 2) {
            return 2;
        }
        if (map.keySet().contains(i)) {
            return map.get(i);
        }
        Integer num = f(i - 1, map) + f(i - 2, map);
        map.put(i, num);
        return num;
    }

    //动态规划

    private static int f2(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }


    //国王黄金问题


    private static int getMostGold(int n, int w, int[] g, int[] p) {
        int[] preResults = new int[p.length];
        int[] results = new int[p.length];

        for (int i = 0; i < n; i++) {
            if (i < p[0]) {
                preResults[i] = 0;
            } else {
                preResults[i] = g[0];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < w; j++) {
                if (j < p[i]) {
                    results[j] = preResults[j];
                } else {
                    results[j] = Math.max(preResults[j], preResults[j - p[i]] + g[i]);
                }
            }
            preResults = results;

        }
        return results[n];
    }

    static class Solution {


    }

}
